#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
const int M = 250;
const int N = 35;
int dp[1000];
int w[M];
int v[N];
int m;
int n;
//int price(int* a, int* b ) {
//	int j = m;
//	for (int i = 1; i<= n; i++)
//		for (; j >= w[i]; j--)
//			dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
//	return dp[j];
//}

int main() {
	cin >> m >> n;
	for(int i=1;i<=n;i++){
		int p;
		int c;
		cin >> p >> c;
		w[i] = p;
		v[i] = c;
	}
	
	for (int i = 1; i <= n; i++)
		for (int j = m; j >= w[i]; j--)
			dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
	cout << dp[m] << endl;
	return 0;
}